#!/usr/bin/env python
# coding: utf-8

"""
@file: dfs.py
@author: cg 
@date: 2019/11/27 6:51
@desc: 深度优先遍历
    pseudo-code
    DFS(graph G, start vertex s):
    // all nodes initially unexplored
    mark s as explored
    for every edge (s, v):
        if v unexplored:
            DFS(G, v)
"""

def dfs_recurse(v, G, visited=[]):
    """
    递归的方式实现图G的深度优先遍历
    :param v: 当前访问节点
    :param G: 图，采用邻接列表的形式来表示
    :param visited: 已访问的节点
    :return:
    """
    if v in visited: # 判断v节点是否被访问
        return 
    else:
        visited.append(v)
        for i in G[v]:
            dfs_recurse(i, G, visited)
    return visited


def dfs_stack(G, start_vertex):
    """
    栈的方式实现图的深度优先遍历
    :param G:
    :param start_vertex: 起始点
    :return:
    """
    s = [start_vertex]
    visited = []
    while len(s) > 0:
        v = s.pop(-1)
        if v in visited:
            continue
        else:
            visited.append(v)
            s.extend(G[v])
    return visited

def dfs_stack_standard(G, start_vertex):
    """
    采用python中标准栈（双向队列）的方式来实现图的深度优先遍历
    :param G: 图
    :param start_vertex: 栈
    :return:
    """
    from collections import deque
    to_visit, visited = deque(), list()
    to_visit.append(start_vertex)
    while len(to_visit) > 0:
        v = to_visit.pop()
        if v in visited:
            continue
        else:
            visited.append(v)
            next_vertexs = G[v]
            to_visit.extend(next_vertexs[::-1]) # 倒着填进去吧，这样第一个节点可以被访问
    return visited

G = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def test():
    print("深度优先遍历（递归实现）", dfs_recurse('A', G))
    print("深度优先遍历（栈实现）", dfs_stack(G,'A'))
    print("深度优先遍历（栈-双向队列的形式-实现）", dfs_stack_standard(G,'A'))

if __name__ == '__main__':
    test()